﻿// 贪心-开区间不相交问题.cpp
//  
// 贪心体现处：子问题每次都选择局部最优解，相关推理过程也保证了最优子结构。
//
// （1）总体代码实现思路：
// 通过一定的区间排序规则，使两两相交的区间之间，应选的区间必定比不应选区间位置靠前，
// 且整体所有的区间按照单侧端点有序排列，则只需要从单侧开始遍历，
// 选择出所有与上一被选择区间不相交的区间即可。
//
// （2）在（1）中，整体所有的区间按照单侧端点有序排列显然容易实现。
// 那么，怎样制定区间排序规则，使两两相交的区间之间，应选的区间必定比不应选区间位置靠前？
// 先来看一个子问题（a）：具有包含与被包含关系的两个区间选择哪个？
// 局部最优解是应选择被包含（长度更小）的区间，以保证有更大空间容纳其他区间。
// 
// （3.1）将整体问题转化为子问题：
// 先将整体所有的区间按照单侧端点有序排列，并除去所有可以被其他区间包含的子区间。
// 按单侧端点x1<x2<x3<x4排序区间，则另一侧端点也会有相同大小关系y1<y2<y<y4
// 引入子问题（b）：如此整体有序的区间序列中，最外侧区间与次外侧区间选择哪个？
// 我们来看，因为最外侧的区间的外侧会有一部分永远不会与其他应选区间相交（反证法：假设后续某应选区间与这个最外侧区间的外侧部分相交，则它一定比这个区间长，与应选区间应二选一短矛盾，从而他不是应选区间），从而与问题无关。
// 从而子问题（b）其实等价于：如此整体有序的区间序列中，最外侧区间去掉最外侧与次外侧区间选择哪个？
// 这其实是子问题（a）的一种情况，而根据子问题（a）的结论，而局部最优解是选择短区间（外侧区间）
// 也就是说，所有与这个最外侧区间相交的区间，都将被丢弃。
// 直到向内发现一个与最外侧区间不相交的区，则这个区间又成为新的最外侧区间，
// 重复解决子问题（b）直至完成整个序列的选择。

//  （3.2）上述（3.1）中的叙述，是将区间序列除去被包含区间的，而实际问题是也有被包含区间在序列之中的，
//  现在修正处理来使加入被包含区间的处理正确。
//  先将整体所有的区间按照单侧端点有序排列，
//  在继续按（3.1）执行剩余步骤时可知，
//  如果被包含区间不与某区间的排序依据侧重合，那么这个被包含区间应当被丢弃，处理无误。
// （根据（3.1）中转化为上一被选择区间去掉外侧的区间与该区间的问题，显然应当选择上一被选择区间）。
//  如果被包含区间与某区间的排序依据侧重合，那么这个被包含区间应当被选择，怎么实现呢？
//  只要在排序的时候，如果两者的排序依据侧重合，那么就按另一侧排序，使得短区间排在前，即可让这个被包含区间被选，而长区间将被丢弃。
//
//  （4）综合以上，整个过程如下：
//  4.1 按一侧端点排序，如果有重合端点，则按区间长度（另一端点）排序 且需要短区间靠近遍历起始一侧。
//  4.2 从一侧开始循环遍历，并且记录上一次选择的区间端点，
//  如果遇到区间与上一选择区间重合，总是保持选择靠外侧先出现的区间。
//  如果遇到的区间与上一选择区间不重合，则更新加入选择并记录这个选择。
//  直至完成这个区间扫描

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct range {
	int l;
	int r;
};

bool cmp(range& a, range&b) {
	if (a.l != b.l) return a.l > b.l; // 左端点从大到小
	return a.r < b.r;
	// 左端点相同，右端点小的在前，也就是区间长度小的在前
	// 保证了同一子问题中，选择的是区间长度最小的。
	// 先选择最小区间后，更长的区间会因为与此区间相交而被抛弃。
}

int main()
{
	vector<range> v;
	{           
		range ra;
		while (cin >> ra.l >> ra.r) {
			v.push_back(ra);
		}
	}
	sort(v.begin(), v.end(), cmp); // 排序，重要步骤
	int ans = 1, lastL = v[0].l;
	for (int i = 0; i < v.size(); i++) {
		if (v[i].r <= lastL) {
			// 此区间与上一个选中区间不相交
			// 选中此区间
			ans++;
			lastL = v[i].l;
		}
	}
	cout << ans << endl;
}

